# include<iostream>

using namespace std;


void countSort(int input[] ,int n, int output[], int max){
    // 创建数组 长度为最大值
    int * countArray = new int[max+1]();
    // 统计每个元素的个数
    for (int i=0; i< n; i++){
        int value = input[i];
        countArray[value] += 1; 
    }
    // 计算每个下标在 b 数组对应的索引
    for (int i = 1; i<=max ; i++){
        countArray[i] += countArray[i-1];
    }

    // 整理 A 对应的位置到B 上
    for (int j = n-1; j>=0; j--){
        int t = input[j];
        // 把A 在 j  的元素 放到B 数组正确的位置上
        output[countArray[t] - 1] = t;
        countArray[t] -= 1;
    }
    
}



int main(){
    int max = 100;
    int n = 14;
    int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
    // 排序后的数组
    int* b = new int[n];
    countSort(a, n, b, max);

    for (int i = 0; i<n; i++ ){
        cout<< b[i] << endl;
    }
    delete [] b;       
    return 0;

}